package com.multimedia.scala.euler

import scala.annotation.tailrec
/*
A number consisting entirely of ones is called a repunit.
We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1,
it can be shown that there always exists a value, k, for which R(k) is divisible by n,
and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.
*/
object Asd129 {
  def main(args : Array[String]) : Unit = {
    /* return a digit that consists of  k '1' */
    def R(k: Int, acc: BigInt = 1): BigInt = {
      if (k<=1) acc
      else R(k-1, acc*10 + 1)
    }
    def Rnext(r: BigInt = 1) = r*10 + 1
    /* check if digit has any common divisors with 10 */
    def divisors10(x: BigInt) = !((x%2==0)||(x%5==0))
    
    @tailrec
    def A(n: BigInt, r: BigInt = 1, max: Int = 10000000): Int = {
      //var r = Rcache(k)
      (n%10).toInt match {
        case 1|3|7|9 => {
          //println("match")
          if (r%n==0||max==0) {
        	  //println(n, r.toString.length)
        	  r.toString.length
          } else {
              A(n, (r*BigInt(10))+1, max-1)
          }
        }
        case _ => {
          //println(n.toString.last)
          A(n, (r*BigInt(10))+1, max-1)
        }
      }
    }
    def check(n:BigInt): BigInt = {
      if (divisors10(n)) A(n)
      else -1
    }
    /*find n, such, that A(n)>1000000 */
    def findA(max: BigInt, n: BigInt = 1): BigInt = {
      if (check(n) > max) n
      else findA(max, n+1)
    }
    var time = java.lang.System.currentTimeMillis()
    println(findA(5000))
    println(java.lang.System.currentTimeMillis - time)
    //println((R(50000)/BigInt(58930475)).toString.size)
    
  }
}
